In some applications, a storage system can provide storage to a connected host system. Examples of such storage systems include the storage systems produced by EMC Corporation of Massachusetts. The storage system can provide a logical storage device (logical unit or LUN) for the host, such that the host can read data from and write data to the LUN. Applications executing on the host can use the LUN as, for example, they would a dedicated physical storage device. The physical storage for the LUN can be provisioned from one or more of the physical storage devices (e.g., magnetic disk drives, solid state drives (“SSDs”), etc.) of the storage system, and the storage system can manage on which physical storage devices data from the LUN are stored in a manner transparent to the host. In some applications, deduplication techniques can be applied to a LUN in order to reduce the amount of space used for storing the LUN's data. Conventional approaches to deduplication for a LUN can lead to inefficient resource utilization.